package java_core.two_array;

/*209. 长度最小的子数组 https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/shuang-zhi-zhen-on-by-jin-ai-yi/
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。*/
public class ChangDuZuiXiaoZiShuZu {
    /*public static void main(String[] args) {
        int[] arr = {2, 3, 0, 2, 4, 0};
        System.out.println(myMinSubArrayLen(7, arr));
        System.out.println(minSubArrayLen1(7, arr));
    }*/


    public static int myMinSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else {
            for (int i = 1; i <= nums.length; i++) {
                for (int j = 0; j < nums.length - i + 1; j++) {
                    if (getArraySum(nums, j, j + i) >= s) {
                        return i;

                    }
                }
            }


        }
        return 0;
    }

    private static int getArraySum(int[] arr, int start, int end) {
        int sum = 0;
        for (int i = start; i < end; i++) {
            sum += arr[i];
        }

        return sum;
    }


        public static int minSubArrayLen1(int s, int[] nums) {
            int n = nums.length;
            if (n == 0) return 0;
            int left = 0, right = 0;
            int min_len = 0;
            int sum_left_to_right = 0;
            while (right < n) {
                sum_left_to_right += nums[right];
                if (sum_left_to_right >= s) {
                    if (min_len == 0) min_len = right - left + 1;//从无到有
                    else min_len = Math.min(min_len, right - left + 1);//两个满足条件的子数组才能比较大小
                    sum_left_to_right -= nums[left];
                    sum_left_to_right -= nums[right];
                    left += 1;//每找到一个子数组，则重置窗口左边界left
                } else {
                    right += 1;
                }
                if (left > right)
                    //left一直增加，right却不增加，以至于left>right，只有一种可能，
                    // 即nums存在一个元素>=s,当right指向该元素时，left会一直增加直到超过right
                    return 1;

            }
            return min_len;

        }

    public int minSubArrayLen(int s, int[] nums) {
        int min = Integer.MAX_VALUE;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int start = i;
            int sum = 0;
            while (start < n) {
                sum += nums[start];
                start++;
                //当前和大于等于 s 的时候结束
                if (sum >= s) {
                    min = Math.min(min, start - i);
                    break;
                }
            }
        }
        //min 是否更新，如果没有更新说明数组所有的数字和小于 s, 没有满足条件的解, 返回 0
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    public int minSubArrayLen2(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        while (right < n) {
            sum += nums[right];
            right++;
            while (sum >= s) {
                min = Math.min(min, right - left);
                sum -= nums[left];
                left++;
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }


    //二分查找
    public int minSubArrayLen3(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] sums = new int[n];
        sums[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sums[i] = nums[i] + sums[i - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int s2 = s - nums[i]; //除去当前数字
            for (int j = i; j < n; j++) {
                //i + 1 到  j 的所有数字和
                if (sums[j] - sums[i] >= s2) {
                    min = Math.min(min, j - i + 1);
                }
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }


}
